/*
 * @Author: CBH37
 * @Date: 2023-01-17 17:14:21
 * @Description: 主程序
 */
#include "main.hpp"

/************ tokenizer 部分 ************/
// `token`可能来源于连接符、运算符、关键字、数字、字符串、符号六部分
void getToken() {
    // 初始化
    token = tok_other;
    tokVal = "";
    while(true) {
        // 单行注释
        if(index <= src.length() - 2
        && src[index] == '/' && src[index + 1] == '/') {
            index += 2;
            
            while(index < src.length() && src[index] != '\n') {
                index ++;
            }

            index ++;
            continue;   // 先跳过本轮循环，防止之后出现的注释被归类为运算符或边界符
        }

        // 多行注释
        if(index <= src.length() - 2
        && src[index] == '/' && src[index + 1] == '*') {
            index += 2;
            while(index <= src.length() - 2
               && src[index] != '*' && src[index + 1] != '/') {
                index ++;
            }

            index += 2;
            continue;
        }

        // 因为处理注释后不会返回还会继续处理出其他`Token`，为了不产生范围溢出，所以判断是否到达文件末尾的代码必须在处理注释的代码之后
        if(index >= src.length()) {
            token = tok_eof;
            return;
        }

        // 处理数字（支持二、八、十六进制）
        if(isdigit(src[index])
        || (src[index] == '.' && index <= src.length() - 2 && isdigit(src[index + 1]))) {
            // 1. 处理二、八、十六进制
            int base = 10;

            // 必须提供两位数字，否则可能会出现段错误，或是将十进制`0`当做八进制的前缀的情况
            if(src[index] == '0' && index + 1 < src.length() && isdigit(src[index + 1])) {
                tokVal += src[index];
                index ++;

                if(src[index] == 'b') {
                    base = 2;
                } else if(src[index] == 'x') {
                    base = 16;
                } else {
                    base = 8;
                }

                tokVal += src[index];
                index ++;
            }

            // 2. 处理数字
            bool hasDot = false;
            while(index < src.length()
               && ((base == 16 && isxdigit(src[index]))
               || (src[index] >= '0' && src[index] <= ('0' + base - 1))
               || src[index] == '.')) {
                if(src[index] == '.') {
                    if(hasDot) {
                        error("number can only have one decimal point");
                    }

                    hasDot = true;
                }

                tokVal += src[index];
                index ++;
            }

            
            // 对于二进制和八进制数，数字长度只有两位说明只有前缀没有内容，所以直接报错
            if(base == 2 && base == 8 && tokVal.length() == 2) {
                error("unexpected number:" + tokVal);
            }

            // 3. 处理指数
            if(index <= src.length() - 2 && tolower(src[index]) == 'e') {
                tokVal += src[index];
                index ++;

                while(index < src.length() && isdigit(src[index])) {
                    tokVal += src[index];
                    index ++;
                }
            }

            token = tok_num;
            return;
        }

        // 处理字符串（默认为多行不转义字符串）
        if(src[index] == '"') {
            index ++;
            while(src[index] != '"') {
                if(src[index] == '\\') {
                    index ++;
                }

                tokVal += src[index];
                index ++;
            }

            index ++;
            token = tok_str;
            return;
        }

        // 处理符号、关键字
        if(isalpha(src[index]) || src[index] == '_') {
            while(isalpha(src[index])
              || isdigit(src[index])
              || src[index] == '_') {
                tokVal += src[index];
                index ++;
            }

            if(keywordTable.count(tokVal) || typeTable.count(tokVal)) {
                return;
            }

            token = tok_ident;
            return;
        }

        if(isspace(src[index])) {
            index ++;
        } else {
            // 通过贪心算法处理连接符和运算符
            // 在有可能符合条件的非空字符区间不断获取最新的当前最长的符合条件的作为结果
            // 从而实现最优解解决分割`token`时出现的包含较短的较长符号被分割为较短的和去除较短符号的较长符号两部分的问题
            std::string target = "";
            while(! isspace(src[index]) && index < src.length()) {
                tokVal += src[index];
                if(connectSymbolTable.count(tokVal) 
                || binaryOpTable.count(tokVal)
                || unaryOpTable.count(tokVal)) {
                    target = tokVal;
                }

                index ++;
            }

            // 目标与初始化值相同说明没有一个符合条件的，说明这些字符都是非法字符，直接报错
            if(target == "") {
                error("unexpected token: " + tokVal);
            }

            // 因为最优解是最终结果，所以将索引设置到最优解之后处，使下次解析于最终结果之后
            index = index - tokVal.length() + target.length();
            tokVal = target;
            return;
        }
    } 
}

/************ Parser部分 ************/
/* 符号表部分 */
void insertSymbol(std::string symbol, std::shared_ptr<SymbolMessage> message) {
    symbolTable[symbolTable.size() - 1][symbol] = message;
}

std::shared_ptr<SymbolMessage> getSymbol(std::string symbol) {
    // 从当前作用域向外搜索符号
    for(int i = symbolTable.size() - 1; i >= 0; i --) {
        if(symbolTable[i].count(symbol)) {
            return symbolTable[i][symbol];
        }
    }

    // 符号不存在直接报错
    error(symbol + " doesn't exist");
}

/* Expr 部分 */
std::shared_ptr<NumAST> NumAST::parser() {
    NlcFile::Num number = std::stold(tokVal);

    // 如果数字为整数，化为整数后应于原数相同没有损耗
    if((long long)number == number) {
        type = std::make_shared<TypeMessage>("int");
    } else {
        type = std::make_shared<TypeMessage>("number");
    }

    std::shared_ptr<NumAST> numAST = std::make_shared<NumAST>(number);
    getToken(); // eat number
    return numAST;
}

void NumAST::codegen() {
    builder.newInstrLoadNum(num);
}

std::shared_ptr<StringAST> StringAST::parser() {
    type = std::make_shared<TypeMessage>("string");

    std::shared_ptr<StringAST> string = std::make_shared<StringAST>(tokVal);
    getToken(); // eat string

    return string;
}

void StringAST::codegen() {
    builder.newInstrLoadString(string);
}

void IdentAST::codegen() {
    if(value) {
        value -> codegen();
        switch(state) {
            case symbol_global: {
                builder.newInstrStoreGlobal(ident);
                break;
            }

            case symbol_local: {
                builder.newInstrStoreLocal(ident);
                break;
            }
        }
    }

    switch(state) {
        case symbol_global: {
            builder.newInstrLoadGlobal(ident);
            break;
        }

        case symbol_local: {
            builder.newInstrLoadLocal(ident);
            break;
        }
    }
}

std::shared_ptr<UnaryExprAST> UnaryExprAST::parser() {
    std::string op = tokVal;
    if(op == "!") {
        type = std::make_shared<TypeMessage>("bool");
    }

    getToken(); // eat op
    std::shared_ptr<UnaryExprAST> value = std::make_shared<UnaryExprAST>(op, expr());

    if(op == "+" || op == "-") {
        // +/- num
        if(! matchType(std::make_shared<TypeMessage>("number"))) {
            error("the operand corresponding to the+or - operator in a unary expression must be of numeric type");
        }
    } else if(op == "!" && type -> name == "void") {
        // ! any（除void）
        error("argument to operator cannot be of type void");
    }

    return value;
}

void UnaryExprAST::codegen() {
    value -> codegen();
    
    if(op == "!") {
        builder.newInstrNot();
    } else if(op == "-") {
        // - num = - 1 * num
        builder.newInstrLoadNum(- 1);
        builder.newInstrMod();
    }
}

/*
 * Value ::= NUM
 *         | STRING
 *         | IDENT
 *         | true / false
 *         | UNARY_OP <expr>
 *         | (<BinaryExpr>)
 */
std::shared_ptr<BaseAST> parseValue() {
    std::shared_ptr<BaseAST> target;
    bool isAssign = true;
    bool isConst = false;
    std::shared_ptr<SymbolMessage> symbol;
    if(token == tok_num) {
        return NumAST::parser();
    } else if(token == tok_str) {
        return StringAST::parser();
    } else if(token == tok_ident) {
        std::string ident = tokVal;
        symbol = getSymbol(ident);
        isAssign = symbol -> isAssign;
        isConst = symbol -> isConst;
        std::shared_ptr<TypeMessage> identType = symbol -> type;

        target = std::make_shared<IdentAST>(ident, symbol -> state);
        getToken(); // eat ident

        if(tokVal == "=") {
            // 判断是否可以赋值，如果为常量且已赋过值则不能再次赋值
            if(isConst) {
                if(isAssign) {
                    error("constant can only be defined once");
                } else {
                    symbol -> isAssign = true;
                }
            }
            getToken(); // eat `=`

            std::shared_ptr<BaseAST> value = expr();
            if(! matchType(identType)) {
                error("the input type does not match the expected type");
            }
        
            target = std::make_shared<IdentAST>(ident, symbol -> state, value);
        }

        type = identType;
    } else if(tokVal == "new") {
        target = NewAST::parser();
    } else if(tokVal == "true" || tokVal == "false") { 
        type = std::make_shared<TypeMessage>("bool");
        bool value = tokVal == "true" ? true : false;

        getToken(); // eat true / false
        return std::make_shared<NumAST>(value);
    } else if(unaryOpTable.count(tokVal)) {
        return UnaryExprAST::parser();
    } else if(tokVal == "(") {
        getToken(); // eat `(`
        std::shared_ptr<BaseAST> value = BinaryExprAST::parser();

        if(tokVal != ")") {
            error("expression format error");
        }
        getToken(); // eat `)`
        target = value;
    } else if(tokVal == "[") {
        target = ListAST::parser();
    } else if(tokVal == "{") {
        target = MapAST::parser();
    } else if(connectSymbolTable.count(tokVal)) {
        return nullptr;
    } else {
        error("expression format error");
    }

    std::shared_ptr<TypeMessage> targetType = type;
    while(true) {
        if(tokVal == "[") {
            getToken(); // eat `[`

            std::string accessType = targetType -> name;
            std::shared_ptr<BaseAST> key = expr();
            if(targetType -> name == "list") {
                // `list`的索引必须为整数
                if(! matchType(std::make_shared<TypeMessage>("int"))) {
                    error("only index of type int can be used to access list");
                }

                targetType = targetType -> args[0];
            } else if(targetType -> name == "map") {
                targetType = targetType -> args[1];
            } else {
                error("only list and map can be accessed by key");
            }

            if(tokVal != "]") {
                error("access expr format error");
            }
            getToken(); // eat `]`

            if(tokVal == "=") {
                if(isConst) {
                    if(isAssign) {
                        error("constant can only be defined once");
                    } else {
                        symbol -> isAssign = true;
                    }
                }
                getToken(); // eat `=`

                std::shared_ptr<BaseAST> value = expr();
                if(! matchType(targetType)) {
                    error("the input type does not match the expected type");
                }
        
                target = std::make_shared<AccessAST>(accessType, target, key, value);
            } else {
                target = std::make_shared<AccessAST>(accessType, target, key);
            }
        } else if(tokVal == ".") {
        } else if(tokVal == "(") {
            if(targetType -> name != "fn" && targetType -> name != "efn") {
                error("only functions can be called");
            }
            getToken(); // eat `(`

            std::vector<std::shared_ptr<BaseAST>> args;

            for(int i = 0; i < targetType -> args.size() - 1; i ++) {
                args.push_back(expr());
                if(! matchType(targetType -> args[i])) {
                    error("the parameters used to call the function do not match the prototype");
                }

                if(tokVal == ",") {
                    getToken(); // eat `,`
                } else if(tokVal == ")") {
                    // 输入参数的数量比原型中参数的数量少则报错，反之听天由命
                    if(i + 1 < targetType -> args.size() - 1) {
                        error("the parameters used to call the function do not match the prototype");
                    }

                    getToken(); // eat `)`
                    break;
                } else {
                    error("call expression format error");
                }
            }

            target = std::make_shared<CallAST>(target, args, targetType -> name == "efn" ? true : false);
            targetType = targetType -> args[targetType -> args.size() - 1]; // 获取最后一个参数，即返回值类型
        } else if(tokVal == ":") {
            if(! actions.count(targetType -> name)) {
                error("no action on type " + targetType -> name);
            }
            getToken(); // eat `:`

            if(token != tok_ident) {
                error("action expression format error");
            }
            std::string actionName = tokVal;
            getToken(); // eat `IDENT`

            if(! actions[targetType -> name].count(actionName)) {
                error("type " + targetType -> name + " has no " + actionName + " action");
            }
            std::vector<std::shared_ptr<TypeMessage>> argTypes = actions[targetType -> name][actionName];
            std::vector<std::shared_ptr<BaseAST>> args;

            if(tokVal != "(") {
                error("action expression format error");
            }
            getToken(); // eat `(`

            for(int i = 0; i < argTypes.size() - 1; i ++) {
                args.push_back(expr());
                if(! matchType(argTypes[i])) {
                    error("the parameters used to call the function do not match the prototype");
                }

                if(tokVal == ",") {
                    getToken(); // eat `,`
                } else if(tokVal == ")") {
                    // 输入参数的数量比原型中参数的数量少则报错，反之听天由命
                    if(i < targetType -> args.size() - 1) {
                        error("the parameters used to call the function do not match the prototype");
                    }

                    getToken(); // eat `)`
                    break;
                } else {
                    error("action expression format error");
                }
            }

            target = std::make_shared<ActionAST>(targetType -> name, target, actionName, args);
            targetType = argTypes[argTypes.size() - 1]; // 同上
        } else {
            break;
        }
    }

    type = targetType;
    return target;
}

void AccessAST::codegen() {
    object -> codegen();

    if(value) {
        key -> codegen();
        value -> codegen();

        if(accessType == "list") {
            builder.newInstrActionList("ASSIGN");
        } else {
            builder.newInstrActionMap("ASSIGN");
        }
    }

    key -> codegen();
    if(accessType == "list") {
        builder.newInstrActionList("GET");
    } else {
        builder.newInstrActionMap("GET");
    }
}

void CallAST::codegen() {
    if(isExtern) {
        // 外部函数使用`list`传参
        builder.newInstrMakeList();
        for(auto arg : args) {
            arg -> codegen();
            builder.newInstrActionList("PUSH");
        }

        object -> codegen();
        builder.newInstrCalle();
    } else {
        // Args
        for(auto arg : args) {
            arg -> codegen();
        }

        builder.newInstrLoadNum(args.size());   // Arg Num
        object -> codegen();    // address
        builder.newInstrCall();
    }
}

// 为了简单起见和灵活性，信任定义的`action`，不对`actionName`和其参数进行检查
void ActionAST::codegen() {
    object -> codegen();
    for(auto arg : args) {
        arg -> codegen();
    }

    if(type == "list")  {
        builder.newInstrActionList(actionName);
    } else {
        builder.newInstrActionMap(actionName);
    }
}

/*
 * BinaryExpr ::= <Value>
 *              | <Value> (OP <Value>)*
 */
std::shared_ptr<BaseAST> BinaryExprAST::parser() {
    std::vector<std::string> opStack;   // 操作符栈
    std::vector<std::pair<std::shared_ptr<BaseAST>, std::shared_ptr<TypeMessage>>> valueStack; // 操作数栈
    valueStack.push_back({ parseValue(), type });
    while(binaryOpTable.count(tokVal)) {
        while(opStack.size() > 0 && binaryOpTable[opStack[opStack.size() - 1]] >= binaryOpTable[tokVal]) {
            // 算数运算符：num + num = num
            if(mathOpTable.count(opStack[opStack.size() - 1])) {
                if(! (matchType(std::make_shared<TypeMessage>("number"), valueStack[valueStack.size() - 1].second)
                && matchType(std::make_shared<TypeMessage>("number"), valueStack[valueStack.size() - 2].second))) {
                    error("the two operands of an arithmetic operator must be of numeric type");
                }

                // int + int = int
                if(matchType(std::make_shared<TypeMessage>("int"), valueStack[valueStack.size() - 1].second)
                && matchType(std::make_shared<TypeMessage>("int"), valueStack[valueStack.size() - 2].second)) {
                    valueStack[valueStack.size() - 2].second -> name = "int";    
                } else {
                    valueStack[valueStack.size() - 2].second -> name = "number";
                }
            } else {
                // 逻辑运算符：any(除void) + any(除void) = bool
                if(valueStack[valueStack.size() - 1].second -> name == "void"
                || valueStack[valueStack.size() - 2].second -> name == "void") {
                    error("argument to operator cannot be of type void");
                }

                valueStack[valueStack.size() - 2].second -> name = "bool";
            }

            valueStack[valueStack.size() - 2].first = std::make_shared<BinaryExprAST>(opStack[opStack.size() - 1], 
                                                                                      valueStack[valueStack.size() - 2].first,
                                                                                      valueStack[valueStack.size() - 1].first);
            valueStack.pop_back();
            opStack.pop_back();
        }

        opStack.push_back(tokVal);
        getToken(); // eat OP
        valueStack.push_back({ parseValue(), type });
    }

    // 当前符号的优先级小于等于栈顶符号的优先级时，计算至当前符号优先级大于栈顶符号的优先级或栈空为止
    // 因此若当前符号的优先级大于栈顶符号的优先级这样的情况持续到解析结束，则操作符栈非空且其中的元素从下至上的优先级以正序排列，因此从后向前处理即可
    for(int i = opStack.size() - 1; i >= 0; i --) {
        if(mathOpTable.count(opStack[i])) {
            if(! (matchType(std::make_shared<TypeMessage>("number"), valueStack[valueStack.size() - 1].second)
            && matchType(std::make_shared<TypeMessage>("number"), valueStack[valueStack.size() - 2].second))) {
                error("the two operands of an arithmetic operator must be of numeric type");
            }

            if(matchType(std::make_shared<TypeMessage>("int"), valueStack[valueStack.size() - 1].second)
            && matchType(std::make_shared<TypeMessage>("int"), valueStack[valueStack.size() - 2].second)) {
                valueStack[valueStack.size() - 2].second -> name = "int";    
            } else {
                valueStack[valueStack.size() - 2].second -> name = "number";
            }
        } else {
            if(valueStack[valueStack.size() - 1].second -> name == "void"
            || valueStack[valueStack.size() - 2].second -> name == "void") {
                error("argument to operator cannot be of type void");
            }
            
            valueStack[i].second -> name = "bool";
        }

        valueStack[i].first = std::make_shared<BinaryExprAST>(opStack[i], valueStack[i].first, valueStack[i + 1].first);
    }

    type = valueStack[0].second;
    return valueStack[0].first;
}

void BinaryExprAST::codegen() {
    left -> codegen();
    right -> codegen();
    if(mathOpTable.count(op)) {
        // 算数运算符
        if(op == "+") {
            builder.newInstrAdd();
        } else if(op == "-") {
            builder.newInstrSub();
        } else if(op == "*") {
            builder.newInstrMul();
        } else if(op == "/") {
            builder.newInstrDiv();
        } else if(op == "%") {
            builder.newInstrMod();
        } else if(op == "**") {
            builder.newInstrPow();
        }
    } else {
        // 逻辑运算符
        builder.newInstrCompare(op);
    }
}

// listStateMent ::= [] | [ <expr> (, <expr>)* ]
std::shared_ptr<ListAST> ListAST::parser() {
    getToken(); // eat `[`

    std::shared_ptr<TypeMessage> listType = std::make_shared<TypeMessage>("list");
    if(tokVal == "]") {
        getToken(); // eat `]`

        listType -> args.push_back(std::make_shared<TypeMessage>("uncertain"));
        type = listType;
        return std::make_shared<ListAST>();
    }
    
    std::vector<std::shared_ptr<BaseAST>> items;
    items.push_back(expr());

    // 因为列表中各项目的类型相同，所以通过获取首项目的类型即可得知列表中所有项目的类型方便类型检查
    std::shared_ptr<TypeMessage> itemType = type;
    listType -> args.push_back(itemType);
    while(tokVal != "]") {
        if(tokVal != ",") {
            error("list format error");
        }

        getToken(); // eat `,`

        items.push_back(expr());
        if(! matchType(itemType)) {
            error("the types of items in the list should be consistent");
        }
    }

    getToken(); // eat `]`
    type = listType;
    return std::make_shared<ListAST>(items);
}

void ListAST::codegen() {
    builder.newInstrMakeList();
    for(auto item : items) {
        item -> codegen();
        builder.newInstrActionList("PUSH");
    }
}

// mapStateMent ::= {} | { <expr> : <expr> (, <expr> : <expr>)* }
std::shared_ptr<MapAST> MapAST::parser() {
    getToken(); // eat `{`

    std::shared_ptr<TypeMessage> mapType = std::make_shared<TypeMessage>("map");
    if(tokVal == "}") {
        getToken(); // eat `}`

        mapType -> args.push_back(std::make_shared<TypeMessage>("uncertain"));
        mapType -> args.push_back(std::make_shared<TypeMessage>("uncertain"));
        type = mapType;

        return std::make_shared<MapAST>();
    }

    // 同`list`
    std::vector<std::shared_ptr<BaseAST>> keys;
    std::vector<std::shared_ptr<BaseAST>> values;

    keys.push_back(expr());
    std::shared_ptr<TypeMessage> keyType = type;
    mapType -> args.push_back(keyType);
    if(! matchType(std::make_shared<TypeMessage>("string"), keyType)) {
        error("the key of the map must be of type string");
    }

    if(tokVal != ":") {
        error("map format error");
    }
    getToken(); // eat `:`

    values.push_back(expr());
    std::shared_ptr<TypeMessage> valueType = type;
    mapType -> args.push_back(valueType);

    while(tokVal != "}") {
        if(tokVal != ",") {
            error("map format error");
        }

        getToken(); // eat `,`

        keys.push_back(expr());
        if(! matchType(keyType)) {
            error("the types of keys in the map should be unified");
        }

        if(tokVal != ":") {
            error("map format error");
        }
        getToken(); // eat `:`

        values.push_back(expr()); 
        if(! matchType(valueType)) {
            error("the types of values in the map should be unified");
        }
    }

    getToken(); // eat `}`
    type = mapType;
    return std::make_shared<MapAST>(keys, values);
}

void MapAST::codegen() {
    builder.newInstrMakeMap();
    for(int i = 0; i < keys.size(); i ++) {
        keys[i] -> codegen();
        values[i] -> codegen();

        builder.newInstrActionMap("ASSIGN");
    }
}

// TypeExpr ::= type | map/ list<{Type, }*>
std::shared_ptr<TypeMessage> parseTypeExpr() {
    if(! typeTable.count(tokVal)) {
        error("type " + tokVal + " doesn't exist");
    }
    std::shared_ptr<TypeMessage> target = std::make_shared<TypeMessage>(tokVal);

    // 处理复杂类型
    if(complexTypes.count(tokVal)) {
        getToken(); // eat ccomplexType
        if(tokVal != "<") {
            error("type expression format error");
        }
        getToken(); // eat `<`

        while(true) {
            target -> args.push_back(parseTypeExpr());

            if(tokVal == ",") {
                getToken(); // eat `,`
            } else if(tokVal == ">") {
                getToken(); // eat `>`
                break;
            } else {
                error("type expression format error");
            }
        }

        if(target -> name == "list" && target -> args.size() != 1) {
            error("list type can only have one type parameter");
        }

        if(target -> name == "map" && target -> args.size() != 2) {
            error("map type must have two type parameters");
        }
    } else {
        getToken(); // eat type
    }


    if(target -> name == "fn" || target -> name == "efn") {
        if(tokVal != ":") {
            error("the function type expression needs to provide an external function");
        }
        getToken(); // eat `:`

        target -> args.push_back(parseTypeExpr());
    }

    return target;
}

bool matchType(std::shared_ptr<TypeMessage> expectType, std::shared_ptr<TypeMessage> inputType) {
    std::string expectTypeName = expectType -> name;
    std::string inputTypeName = inputType -> name;

    // 数字类型重量表：数字类型中能表示数字种类最多的类型越重，对应的数字越大，用于隐性类型转换
    std::map<std::string, int> numTypeWeightTable = {
        { "number", 3 }, { "int", 2 }, { "bool", 1 },
    };

    // 对于类型名相同类型相同的
    if(inputTypeName == expectTypeName) {
        // 复杂类型必须进一步处理
        if(complexTypes.count(inputTypeName)) {
            if(inputType -> args.size() != expectType -> args.size()) {
                return false;
            }

            for(int i = 0; i < inputType -> args.size(); i ++) {
                // 当`map`和`list`的类型参数中出现了`uncertain`说明该`map`和`list`为空表，可以被任何类型的`map`和`list`所接受
                if(inputType -> args[i] -> name == "uncertain") {
                    continue;
                }

                // 当`inputType`和`expectType`的类型参数不一致时，匹配失败
                if(! matchType(expectType -> args[i], inputType -> args[i])) {
                    return false;
                }
            }
        }

        return true;
    } else if(numTypeWeightTable.count(expectTypeName) && numTypeWeightTable.count(inputTypeName)) {
        // `exepctType`必须比`inputType`表示的数字种类相等或多才能容纳`inputType`
        if(numTypeWeightTable[expectTypeName] > numTypeWeightTable[inputTypeName]) {
            return true;
        } 

        return false;
    } else if(expectTypeName == "any") {
        // `any`可以接受任何类型，所以`expectType`肯定可以接受`inputType`
        return true;
    } else {
        return false;
    }
}

// 判断当前是否在全局
bool isGlobal() {
    return symbolTable.size() == 1 ? true : false; // 若符号表的长度为1，说明符号表与开始一样，没有加层，说明在全局
}

// defStateMent ::= let/ const IDENT : TYPE(= <expr>);
std::shared_ptr<DefAST> DefAST::parser() {
    SymbolState state;
    if(isClassMember) {
        state = symbol_member;
    } else {
        state = symbolTable.size() == 1 ? symbol_global : symbol_local; 
    }
    bool isConst = tokVal == "const" ? true : false;
    getToken(); // eat let/ const

    if(token != tok_ident) {
        error("let statement format error");
    }
    std::string name = tokVal;
    getToken(); // eat IDENT

    if(tokVal != ":") {
        error("let statement format error");
    }
    getToken(); // eat `:`

    std::shared_ptr<TypeMessage> symbolType = parseTypeExpr();
    std::shared_ptr<DefAST> target;
    bool isAssign = false;
    if(tokVal == ";") {
        getToken();
        target = std::make_shared<DefAST>(name, isConst, state);
    } else if(tokVal == "=") {
        isAssign = true;
        getToken(); // eat `=`

        std::shared_ptr<BaseAST> value = expr();
        if(tokVal != ";") {
            error("let statement format error");
        }
        getToken(); // eat `;`

        if(! matchType(symbolType)) {
            error("the input type does not match the expected type (symbol " + name + ")");
        }

        target = std::make_shared<DefAST>(name, value, isConst, state);
    } else {
        error("let statement format error");
    }

    // 类成员不需要插入符号表
    if(state != symbol_member) {
        insertSymbol(name, std::make_shared<SymbolMessage>(symbolType, state, isConst, isAssign));
    }
    return target;
}

void DefAST::codegen() {
    if(value) {
        value -> codegen();
        
        switch(state) {
            case symbol_global: {
                builder.newInstrStoreGlobal(name);
                return;
            }

            case symbol_local: {
                builder.newInstrStoreLocal(name);
                return;
            }

            case symbol_member: {
                builder.newInstrLoadString(name);
                builder.newInstrActionMap("ASSIGN");
                return;
            }
        }
    }
}

// prototype ::= fn/ extern IDENT( { IDENT : <typeExpr>, }* ) -> returnType
Prototype parsePrototype() {
    Prototype target;

    bool isExtern = tokVal == "fn" ? false : true;
    std::string typeName = tokVal == "extern" ? "efn" : "fn";
    getToken(); // eat `fn`/ `extern`

    if(token != tok_ident) {
        error("prototype format error");
    }
    target.fnName = tokVal;
    getToken(); // eat fnName

    if(tokVal != "(") {
        error("prototype format error");
    }
    getToken(); // eat `(`

    while(true) {
        if(token != tok_ident) {
            error("prototype format error");
        }
        target.argNames.push_back(tokVal);
        getToken(); // eat argName

        if(tokVal != ":") {
            error("prototype format error");
        }
        getToken(); // eat `:`

        
        target.argTypes.push_back(parseTypeExpr());
        if(tokVal == ",") {
            getToken();
        } else if(tokVal == ")") {
            getToken();
            break;
        } else {
            error("prototype format error");
        }
    }

    // return type
    if(tokVal != ":") {
        error("prototype format error");
    }
    getToken(); // eat `:`

    target.argTypes.push_back(parseTypeExpr()); // 为了方便起见，将返回类型存储至参数类型之后
    if(! isClassMember) {
        insertSymbol(target.fnName, std::make_shared<SymbolMessage>(std::make_shared<TypeMessage>(typeName, isExtern, target.argTypes), symbol_global));
    }
    
    return target;
}

// fnDef ::= <prototype> <subpart>
std::shared_ptr<FnAST> FnAST::parser() {
    if(isGlobal() != true && isClassMember != true) {
        error("function must be global");
    }

    Prototype prototype = parsePrototype();
    symbolTable.resize(symbolTable.size() + 1);
    for(int i = 0; i < prototype.argNames.size(); i ++) {
        insertSymbol(prototype.argNames[i], std::make_shared<SymbolMessage>(prototype.argTypes[i], symbol_local));
    }

    currentFn = std::make_shared<Prototype>(prototype);
    isClassMember = false;  // 只有类下第一层为成员
    std::vector<std::shared_ptr<BaseAST>> body = parseSubpart();
    isClassMember = true;
    currentFn = nullptr;

    symbolTable.pop_back();
    return std::make_shared<FnAST>(prototype, body, isClassMember);
}

void FnAST::codegen() {
    std::shared_ptr<Nbd::Block> mainBlock = builder.insertBlock;    // 保存现场，插入代码后再恢复
    std::shared_ptr<Nbd::Block> insertBlock = builder.newBlock(prototype.fnName);
    builder.setInsertBlock(insertBlock);

    // 调用函数时会将参数压到新建的栈帧上，需要`store_local`将其值加载到各参数变量中
    for(auto argName : prototype.argNames) {
        builder.newInstrStoreLocal(argName);
    }
    codegenSubpart(body);   // 生成主体
    
    // 对于返回值为`void`类型的函数而言，一般来说不会使用显性`return`来返回，所以增加冗余返回语句自动返回
    // 对于其他类型，为了令用户及时发现错误以及实现的简便，不增加冗余返回语句自动返回
    if(prototype.argTypes[prototype.argTypes.size() - 1] -> name == "void") {
        builder.newInstrLoadNum(0);
        builder.newInstrRet();
    }

    // 将函数地址存储到与其同名的变量中，从而统一调用函数的方式并方便将函数赋值给其他变量
    builder.setInsertBlock(mainBlock);  // 恢复插入点
    builder.newInstrLoadAddr(insertBlock);
    if(isInClass) {
        builder.newInstrLoadString(prototype.fnName);
        builder.newInstrActionMap("ASSIGN");
    } else {
        builder.newInstrStoreGlobal(prototype.fnName);
    }
}

// returnStateMent ::= return <expr>
std::shared_ptr<ReturnAST> ReturnAST::parser() {
    if(currentFn == nullptr) {
        error("the return statement can only be used in the function body");
    }
    getToken(); // eat `return`

    std::shared_ptr<BaseAST> value;
    if(currentFn -> argTypes[currentFn -> argTypes.size() - 1] -> name == "void") {
        // 虽然返回值类型为`void`，但为了实现简便，`return`语句对应的`RET`指令必须返回一个值
        // 而且`void`类型的值无法与其他类型的值相运算，所以多加载一个值对程序的运行并不会产生影响，所以遇到返回值类型为`void`时默认返回数字`0`
        value = std::make_shared<ReturnAST>(std::make_shared<NumAST>(0));
    } else {
        value = expr();

        if(! matchType(currentFn -> argTypes[currentFn -> argTypes.size() - 1])) {
            // 函数返回值的类型必须接受`return`语句返回的值
            error("the function return type must be the same as the `return` return type");
        }
    }

    if(tokVal != ";") {
        error("return statement format error");
    }
    getToken(); // eat `;`

    return std::make_shared<ReturnAST>(value);
}

void ReturnAST::codegen() {
    value -> codegen();
    builder.newInstrRet();
}

// subpart ::= { <parser> } | <parseStatement>
std::vector<std::shared_ptr<BaseAST>> parseSubpart() {
    if(tokVal == "{") {
        std::vector<std::shared_ptr<BaseAST>> target = parser();
        if(tokVal != "}") {
            error("statement block format error");
        }
        getToken(); // eat `}`

        return target;
    } else {
        return { parseStatement() };
    }
}

// importStateMent ::= import <expr>
std::shared_ptr<ImportAST> ImportAST::parser() {
    getToken(); // eat `import`

    std::shared_ptr<ImportAST> target = std::make_shared<ImportAST>(expr());
    if(! matchType(std::make_shared<TypeMessage>("string"))) {
        error("the parameter of the import statement must be of type string");
    }

    if(tokVal != ";") {
        error("the import statement must start with `;` ending");
    }
    getToken(); // eat `;`

    return target;
}

void ImportAST::codegen() {
    name -> codegen();
    builder.newInstrImport();
}

void NopAST::codegen() {
    builder.newInstrNop();
}

// classDef ::= class IDENT (extend IDENT) { <defStatement> | }
void parseClass() {
    if(! isGlobal()) {
        error("classes can only be defined globally");
    }
    getToken(); // eat `class`

    if(token != tok_ident) {
        error("class format error");
    }

    if(classTable.count(tokVal)) {
        error("class cannot be defined repeatedly");
    }
    std::string name = tokVal;
    getToken(); // eat IDENT

    if(tokVal == "extend") {
        getToken(); // eat `extend`

        if(token != tok_ident) {
            error("class format error");
        }

        if(! classTable.count(tokVal)) {
            error("class "+ name + " inherits classes that do not exist");
        }
    }
    
    if(tokVal != "{") {
        error("class format error");
    }
    getToken(); // eat `{`

    isClassMember = true;
    while(tokVal != "}") {
        if(tokVal == "let" || tokVal == "const") {
            std::shared_ptr<DefAST> target = DefAST::parser();
            target -> getName();
        }
    }
}

std::shared_ptr<NewAST> NewAST::parser() {
    getToken(); // eat `new`

    if(token != tok_ident) {
        error("new statement format error");
    }

    getToken(); // eat IDENT
}

void NewAST::codegen() {

}

// actionDefStatement ::= action map/ list: IDENT({ <typeExpr>, }) : <typeExpr>
void parseActionDef() {
    getToken(); // eat `action`

    // 现在只支持操作`map`和`list`
    if(tokVal != "map" && tokVal != "list") {
        error("action statement: only map and list actions are supported");
    }
    std::string actionType = tokVal;
    getToken(); // eat TYPE

    if(tokVal != ":") {
        error("action statement format error");
    }
    getToken();

    if(token != tok_ident) {
        error("action statement format error");
    }
    std::string actionName = tokVal;
    getToken(); // eat IDENT

    if(tokVal != "(") {
        error("action statement format error");
    }
    getToken(); // eat `(`
    std::vector<std::shared_ptr<TypeMessage>> types;
    while(true) {
        types.push_back(parseTypeExpr());

        if(tokVal == ",") {
            getToken();
        } else if(tokVal == ")") {
            getToken();
            break;
        } else {
            error("action statement format error");
        }
    }

    // return type
    if(tokVal != ":") {
        error("action statement format error");
    }
    getToken(); // eat `:`

    types.push_back(parseTypeExpr());   // 同原型

    if(tokVal != ";") {
        error("action statement format error");
    }
    getToken(); // eat `;`

    if(! actions.count(actionType)) {
        std::map<std::string, std::vector<std::shared_ptr<TypeMessage>>> target;
        actions[actionType] = target;
    }

    actions[actionType][actionName] = types;
}

std::vector<std::shared_ptr<BaseAST>> parser() {
    std::vector<std::shared_ptr<BaseAST>> statements;
    getToken();
    while(token != tok_eof && tokVal != "}") {
        statements.push_back(parseStatement());
    }

    // 若处理结束已经到达程序末尾，说明处理的是整个程序
    if(token == tok_eof) {
        program = statements;
    }

    return statements;
}

std::shared_ptr<BaseAST> parseStatement() {
    while(token != tok_eof) {
        if(tokVal == "let" || tokVal == "const") {
            return DefAST::parser();
        } else if(tokVal == "fn") {
            return FnAST::parser();
        } else if(tokVal == "extern") {
            parsePrototype();

            if(tokVal != ";") {
                error("the extern statement starts with `;` ending");
            }
            getToken();
        } else if(tokVal == "import") {
            return ImportAST::parser();
        } else if(tokVal == "action") {
            parseActionDef();
        } else if(tokVal == "return") {
            return ReturnAST::parser();
        } else if(tokVal == "class") {
        } else {
            std::shared_ptr<BaseAST> target = expr();

            if(tokVal != ";") {
                error("the statement should start with `;` ending");
            }
            getToken(); // eat `;`

            return target;
        }
    }

    // 遇到不生成代码的语句，循环不断进行直到找到生成代码的语句，如果到了结尾仍未找到，使用空语句搪塞过去即可
    return std::make_shared<NopAST>();
}

void codegenSubpart(std::vector<std::shared_ptr<BaseAST>> statements) {
    for(auto statement : statements) {
        statement -> codegen();
    }
}

void codegen() {
    std::shared_ptr<Nbd::Block> mainBlock = builder.newBlock("main");
    builder.setBeginBlock(mainBlock);
    builder.setInsertBlock(mainBlock);

    codegenSubpart(program);
}

int main(int argc, char** argv) {
    // 读取文件并
    std::ifstream in("test.nl");
    std::ostringstream tmp;
    tmp << in.rdbuf();
    src = tmp.str();/*
    while(token != tok_eof) {
        getToken();
        std::cout << tokVal << '\n';
    }*/
    parser();

    // 生成`nl`汇编
    codegen();
    std::string code = builder.codegen();
    std::cout << code << "\n";

    // 汇编并运行
    Nas as(code, "test.nlc");
    Nvm vm("test.nlc");

    return 0;
}
